package leetcode.code1029;

import java.util.Arrays;

public class Solution {

	public int twoCitySchedCost(int[][] costs) {
		Arrays.sort(costs, (a, b) -> Math.abs(b[0] - b[1]) - Math.abs(a[0] - a[1]));
		int n = costs.length;
		int a = n >> 1, b = n >> 1, ans = 0;
		for (int i = 0; i < costs.length; i++) {
			int[] cost = costs[i];
			int ai = cost[0], bi = cost[1];
			if (a > 0 && b > 0) {
				if (ai < bi) {
					a -= 1;
					ans += ai;
				} else {
					b -= 1;
					ans += bi;
				}
			} else if (a > 0) {
				a -= 1;
				ans += ai;
			} else {
				b -= 1;
				ans += bi;
			}
		}
		return ans;
	}
}
